//
// Created by dengspc on 2019/2/13.
//

/*
 * 无向图：边无向
 * 自环：一条连接一个顶点和其自身的边
 * 平行边：连接同一对顶点的两条边称为平行边
 * 简单无向图：没有自环且没有平行边的图
 * 多重图：含有平行边的无向图
 * 路径：由边顺序连接的一系列顶点
 * 简单路径：没有重复顶点的路径
 * 环：至少含有一条边且起点和终点相同的路径
 * 简单环：不含有重复顶点重复边的环
 * 联通的，指两顶点直接有路径相连
 * 连通图：任意顶点都存在一条路径到另外任意节点
 * 极大连通子图：一副非连通的图由若干联通图组成，他们都是
 * 无环图：不包含环的无向图
 * 树是无环连通图
 * 稀疏图：E（edge 边) 远远小于 1/2*V*V(V vertex 顶点)
 * 稠密图：E（edge 边) 接近于 1/2*V*V(V vertex 顶点)
 * 二分图：将图所有顶点分为两组，两组中的节点不能直接相连 则称
 *         or  至少有两个顶点，且其所有回路的长度均为偶数，任何无回路的的图均是二分图
 *
 *  图的表示方法：
 *    条件：
 *      1，能为各种类型图预留空间
 *      2，各种实现一定要快
 *
 *   表示：
 *      1，邻接矩阵 （不满足1条件，百万级别的顶点，空间将达到万亿级别。不支持平行边）
 *      2，边数组 （不满足2条件，adj实现将遍历图中所有边数组）
 *      3，邻接表数组 （满足，使用数组+链表）
 */

#ifndef INC_010_ALGORITHM_GRAPH_H
#define INC_010_ALGORITHM_GRAPH_H

#include <ostream>
#include <vector>
#include <stack>

using namespace std;

class DiGraph {
public:
    virtual int V() = 0;//求顶点数量
    virtual int E() = 0;//求边数量
    virtual void addEdge(int v, int w) = 0;//向图中添加一条边 v w
    virtual vector<int>* adj(int v) = 0;//与v相邻的顶点集合
    virtual void print() = 0;//打印
    virtual int numOfSelfLoops() = 0 ;//计算自环的个数


/**
 * 计算v的度数
 * @param G
 * @param v
 */
    int degree(int v) {
        vector<int>* valList = adj(v);
        int size =  valList->size();
        delete valList;
        return size;
    }

/**
 * 计算G的最大度数
 * @param G
 * @return
 */
    int maxDegree() {
        int max = 0;
        for (int i = 0; i < V(); i++) {
            int idegree = degree(i);
            max = idegree > max ? idegree : max;
        }
        return max;
    }

/**
 * 求平均度数
 * @param G
 * @return
 */
    double avgDegree() {
        return 2 * E() / V();
    }


};

/**
 * 图处理算法
 */
class Search{
public:
    virtual bool marked(int v) = 0;//v 与 source 是否连通
    virtual int size() = 0; // 与 source联通的source总数
};

/**
 * 图路径算法
 */
class Paths{
protected:
    bool* marks;//标记对应点是否被访问过 true = 访问过
    int* edges;//边集合，类似18-uf工程中的并查集，不断递归，最终指向source edges[?] = source。总体来说存储路径
    int source;//目标顶点
public:
    bool hasPathTo(int v){
        return marks[v];
    }//v 与 source 是否存在路径
    stack<int>* pathTo(int v) {
        if(!hasPathTo(v)) return NULL;
        stack<int>* stack1 = new stack<int>();
        for(int x = v; x != source; x = edges[x]){
            stack1->push(x);
        }
        stack1->push(source);
        return stack1;

    } // 与 source 与v 的路径

};


/**
 * 图连通分量
 */
class CC{
public:
    virtual bool connected(int v, int w) = 0;//v 与 w 是否连通
    virtual int count() = 0; // 连通分量数
    virtual int id(int v) = 0; // v所在连通分量的顶点(标识符)
};

/**
 * 图存在环？（平行边和自环不算）
 */
class Cycle{
public:
    virtual bool hasCycle() = 0;//v 与 w 是否连通
};

/**
 * 图为二分图？
 */
class TwoColor{
public:
    virtual bool isBipartite() = 0;//
};

#endif //INC_010_ALGORITHM_GRAPH_H
